package leetcode.newVersion.window;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class lc438 {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        if (s.length() < p.length()) return ans;

        int size = p.length();
        HashMap<Character, Integer> mapP = new HashMap<>();
        for (char c : p.toCharArray()) {
            mapP.put(c, mapP.getOrDefault(c, 0) + 1);
        }

        HashMap<Character, Integer> mapS = new HashMap<>();

        for (int right = 0; right < s.length(); right++) {
            char rightC = s.charAt(right);
            mapS.put(rightC, mapS.getOrDefault(rightC, 0) + 1);

            if (right >= size){//窗口长度大于p的长度，应该将窗口最左边的元素移除
                char leftC = s.charAt(right-size);
                //先查询leftC的数量，然后将数量-1.若数量为0，则移除
                //比如窗口中为‘aaa’，只想要移除最左侧的一个，不能直接使用remove，将会将3个‘a’全部清除
                //应该在数量为0时remove
                mapS.put(leftC, mapS.getOrDefault(leftC, 0) - 1);
                if (mapS.get(leftC) == 0){
                    mapS.remove(leftC);
                }
            }

            //当mapS和mapP相同时，符合条件.向ans中增添起始的索引
            if (right >= size-1 && mapS.equals(mapP)){
                ans.add(right-size+1);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        lc438 sol = new lc438();
        String s1 = "cbaebabacd";
        String p1 = "abc";
        String s2 = "abab";
        String p2 = "ab";
        System.out.println(sol.findAnagrams(s1, p1));
        System.out.println(sol.findAnagrams(s2, p2));
    }
}
